[LeetCode] 62 - Unique Paths

題意

機器人每次可以往下或往右走，請問到最右下角最多會有幾種走法。

解法

DP，假設dp(i,j)代表從起點到座標(i,j)的走法，我們可以得到下式

dp(i,j) = dp(i-1,j) + dp(i,j-1)

程式

class Solution {
public:
	int uniquePaths(int m, int n) {
		int table[m][n] ;
		for ( int i = 0 ; i < m ; i ++ )
			table[i][0] = 1 ;
		for ( int i = 0 ; i < n ; i ++ )
			table[0][i] = 1 ;
		for ( int i = 1 ; i < m ; i ++ ){
			for ( int j = 1 ; j < n ; j ++ )
				table[i][j] = table[i-1][j] + table[i][j-1] ;
		}
		return table[m-1][n-1] ;
	}
};